public class AVLTree {
    static class TreeNode{
        public int val;//节点的值
        public int bf;//平衡因子
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode parent;//父亲节点
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root;//根节点
    //节点的插入
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        //若根节点为空，则直接将插入为根节点
        if(root == null){
            root = node;
            return true;
        }
        //根节点不为空，查找其插入位置
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > val){
                parent = cur;
                cur = cur.left;
            }else{
                return false;//若已有该节点，则插入失败，直接返回false
            }
        }
        //将节点插入
        node.parent = parent;
        cur = node;
        return true;
    }
    //右单旋
    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
            subLR.parent = parent;
        }

        subL.right = parent;
        //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //判断subL是否被修改为根节点
        if(parent == root){
            root = subL;
            root.parent = null;
        }else {
            subL.parent = pParent;
            //判断是左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subL;
            }else {
                parent.right = subL;
            }
        }
        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }
    //左单旋
    private void rotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
            subRL.parent = parent;
        }

        subR.left = parent;
        //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        //判断subR是否被修改为根节点
        if(parent == root){
            root = subR;
            root.parent = null;
        }else {
            //判断是其左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        //修改平衡因子
        subR.bf = 0;
        parent.bf = 0;
    }
}